export default function solveSudoku(
	type: string,
	boardOld: Array<Array<number | null>>
): Array<Array<Array<number | null>>> {
	const board: Array<Array<number | null>> = JSON.parse(
		JSON.stringify(boardOld)
	);
	const numType: number = parseInt(type);
	const line: boolean[][] = Array.from({ length: numType }, () =>
		Array(numType).fill(false)
	);
	const column: boolean[][] = Array.from({ length: numType }, () =>
		Array(numType).fill(false)
	);
	const index = [4, 6, 9].indexOf(numType);
	const lenA = [2, 3, 3][index];
	const lenB = [2, 2, 3][index];
	const block: boolean[][][] = Array.from({ length: lenA }, () =>
		Array.from({ length: lenB }, () => Array(numType).fill(false))
	);
	const spaces: number[][] = [];
	const result: Array<Array<Array<number | null>>> = [];

	// 初始化状态
	for (let i = 0; i < numType; i++) {
		//y
		for (let j = 0; j < numType; j++) {
			//x
			if (board[i][j] === null) {
				spaces.push([i, j]);
			} else {
				const digit = board[i][j]! - 1;
				line[i][digit] = true;
				column[j][digit] = true;
				block[Math.floor(i / lenB)][Math.floor(j / lenA)][digit] = true;
			}
		}
	}

	// 深度优先搜索函数
	function dfs(pos: number): boolean {
		if (pos === spaces.length) {
			result.push(JSON.parse(JSON.stringify(board)));
			return true;
		}
		const [i, j] = spaces[pos];
		for (let digit = 0; digit < numType; digit++) {
			if (
				!line[i][digit] &&
				!column[j][digit] &&
				!block[Math.floor(i / lenB)][Math.floor(j / lenA)][digit]
			) {
				line[i][digit] = true;
				column[j][digit] = true;
				block[Math.floor(i / lenB)][Math.floor(j / lenA)][digit] = true;
				board[i][j] = digit + 1;

				if (dfs(pos + 1)) {
					//return true;
				}

				// 回溯
				line[i][digit] = false;
				column[j][digit] = false;
				block[Math.floor(i / lenB)][Math.floor(j / lenA)][digit] = false;
				board[i][j] = null;
			}
		}
		return false;
	}

	dfs(0);
	return result;
}
